#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
//给定一个头节点为head的非空单链表，返回链表的中间结点
//如果有两个中间结点，则返回第二个中间结点

struct ListNode
{
	int val;
	struct ListNode* next;
};


//快慢指针法
//slow每走一步，fast就走两步
//链表节点为奇数时，当fast走到尾就结束
//链表节点为偶数时，当fast走到尾的下一个节点，也就是空时就结束
struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

//循环遍历法
// 首先通过一个while循环，遍历整个链表，计算链表节点个数
// 通过if else预计判断链表节点个数为奇数还是偶数
// 如果是偶数就遍历取nums/2+1位置的节点为新链表的头节点
// 如果是奇数就遍历取(nums+1)/2位置的节点为新链表的头节点
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* cur=head;
    int nums=1;
    while(cur->next)
    {
        nums++;
        cur=cur->next;
    }
    if(nums%2==0)//偶数
    {
        struct ListNode* evenNode=head;
        for(int even=1;even<nums/2+1;even++)
        {
            evenNode=evenNode->next;
        }
        return evenNode;
    }
    else//奇数
    {
        struct ListNode* oddNode=head;
        for(int odd=1;odd<(nums+1)/2;odd++)
        {
            oddNode=oddNode->next;
        }
        return oddNode;
    }
}